home *** CD-ROM | disk | FTP | other *** search
/ Language/OS - Multiplatform Resource Library / LANGUAGE OS.iso / glass / glass.lha / GLASS / glammar / gg12.c < prev    next >
C/C++ Source or Header  |  1991-01-21  |  7KB  |  266 lines
  1. /*
  2.  
  3.     This file is a part of the GLAMMAR source distribution 
  4.     and therefore subjected to the copy notice below. 
  5.     
  6.     Copyright (C) 1989,1990  Eric Voss, ericv@cs.kun.nl 
  7.  
  8.     This program is free software; you can redistribute it and/or modify
  9.     it under the terms of the GNU General Public License as published by
  10.     the Free Software Foundation version 1
  11.  
  12.     This program is distributed in the hope that it will be useful,
  13.     but WITHOUT ANY WARRANTY; without even the implied warranty of
  14.     MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
  15.     GNU General Public License for more details.
  16.  
  17.     You should have received a copy of the GNU General Public License
  18.     along with this program; if not, write to the Free Software
  19.     Foundation, Inc., 675 Mass Ave, Cambridge, MA 02139, USA.
  20. */
  21. /*  
  22.  **********
  23.  * file  : optimize memoizer benefits by making empties 
  24.  *                  explicite
  25.  * created: Wed Jul 25 16:45:09 MET DST 1990
  26.  *
  27.  * In order to increase memoizer speedup we consider to 
  28.  * turn empties in empty onlies.
  29.  * For instance if we could transform:
  30.  *   a : b ; c.   (1)
  31.  *   b: "b"; .
  32.  *   c :"c"; .
  33.  *  
  34.  * in something like:
  35.  *   a : ip(ip>), b, c , false (>ip);  (2)
  36.  *   a : b'; c'.
  37.  *   b: "b"; .
  38.  *   b': .
  39.  *   c :"c"; .
  40.  *   c': .
  41.  *
  42.  * a major memoizer gain could be expected  since (2) could 
  43.  * benifit from memoizing while  (1) does not because it produces
  44.  * empty.
  45.  * In (2) false(>ip) succeeds if (2) not recognized empty .
  46.  *********
  47.  *
  48.  */
  49.  
  50. #include "gg1.h"
  51. #include "gg2.h"
  52. static int             last_alt = true;
  53. static int             last_empty_alt = nil,empty_rule= nil;
  54. static int             first_empty_rule= nil,last_empty_rule=0;
  55.  
  56. memopt() {
  57.      int r;
  58.      make_empty_alts_empty_only();
  59.      if (first_empty_rule != nil) {
  60.        link_empty_rules();
  61.        for (r = root; BROTHER(r) != init_one_star; r = BROTHER(r));
  62.        BROTHER(last_empty_rule ) = init_one_star;
  63.        BROTHER(r) = first_empty_rule;
  64.      }
  65.     else fprintf(stderr,"No empty alts?\n");
  66. }
  67.  
  68. char *short_repr();
  69. char *new_repr();
  70. char *ipterm = "ip_";
  71.  
  72. make_empty_alts_empty_only()
  73. {
  74.    int alt,rule,mem,last_alt;
  75.    for (rule = root; rule != init_one_star ; rule = BROTHER (rule))
  76.       if (MARKED(rule, emptyrule)) {
  77.          empty_rule = nil;
  78.          last_alt = nil;
  79.          alt = SON(rule);
  80.          if (SON(alt) == nil && BROTHER(alt) == nil) {
  81.                add_empty_only_alt_to_shadow(rule,alt);
  82.                continue;
  83.          }
  84.          for (; alt != nil  ; alt = BROTHER(alt)) {
  85.             for (mem = SON(alt); mem != nil  ; mem = BROTHER(mem))
  86.                if (MARKED(DEF(mem), notemptyrule)) break;
  87.             if (mem == nil) {
  88.                add_empty_only_alt_to_shadow(rule,alt);
  89.  
  90.                if (SON(alt) == nil)  { 
  91.                   if (last_alt == nil)
  92.                      SON(rule) = BROTHER(alt);
  93.                   else 
  94.                      BROTHER(last_alt) = BROTHER(alt);
  95.                } else  {
  96.                   /*    get ip  (ip>)  */
  97.                   newnode(affixnt, nil, nil, ipterm);
  98.                   newnode(derived, nil, brother, "(nil)");
  99.                   newdefnode(ntnode, SON(alt), brother, getip, REPR(getip));
  100.                   SON(alt) = brother;
  101.  
  102.                   for (mem = SON(alt); BROTHER(mem) != nil; mem = BROTHER(mem));
  103.  
  104.                   /*    false ip(>ip)  */
  105.                   newnode(affixnt, nil, nil, ipterm);
  106.                   newnode(inherited, nil, brother, "(nil)");
  107.                   newdefnode(ntnode, nil, brother, falseip, REPR(falseip));
  108.                   BROTHER(mem) =  brother;
  109.                }
  110.             }
  111.             last_alt = alt;
  112.          }
  113.          for (last_alt = SON(rule) ; BROTHER(last_alt) != nil; 
  114.                    last_alt = BROTHER(last_alt));
  115.          add_final_empty_alt(last_alt);
  116.       }
  117. }
  118.  
  119. add_final_empty_alt(alt)
  120. int alt;
  121. {
  122.    int d1 , d2;
  123.    brother = nil;
  124.    new_display(AFFIXDEF(alt),0); 
  125.    d1 = brother;
  126.    brother = nil;
  127.    new_display(AFFIXDEF(alt),0); 
  128.    d2 = brother;
  129.    
  130.    newdefnode (ntnode,nil,d2,last_empty_rule,REPR(last_empty_rule));
  131.    newnode(d1,nil,brother,"nil");
  132.    BROTHER(alt) = brother;
  133. }
  134.  
  135. new_display(afx,count) 
  136. int afx,count;
  137. {
  138.    int b;
  139.    if (afx == nil) return;
  140.    new_display(BROTHER(afx),count+1);
  141.    b = brother;
  142.    newnode (affixnt,nil,nil,short_repr(count));
  143.    newnode (NODENAME(afx),b,brother,"nil");
  144. }
  145.  
  146. add_empty_only_alt_to_shadow(rule,alt)
  147. int alt,rule;
  148. {
  149.          int b ;
  150.          brother = nil;
  151.  
  152.          shadow_empty_mems(SON(alt));
  153.          if (empty_rule != nil && no_derived_afx(AFFIXDEF(alt) )  ) return;
  154.  
  155.          newnode (NODENAME(alt),nil,brother,REPR(alt)); 
  156.          if (empty_rule == nil)  {
  157.            last_empty_alt = brother;
  158.            newnode (NODENAME(rule),nil,brother,new_repr(REPR(rule))); 
  159.            if (MARKED(root,docompile))
  160.               SET(brother,docompile);
  161.  
  162.            empty_rule = brother;
  163.            if (first_empty_rule == nil) {
  164.                last_empty_rule =  brother;
  165.                first_empty_rule =  brother;
  166.            }
  167.            else {
  168.             BROTHER(last_empty_rule) = brother;
  169.             last_empty_rule = brother;
  170.           }
  171.          }
  172.          else  {
  173.            BROTHER(last_empty_alt) = brother;
  174.            last_empty_alt = brother;
  175.          }
  176. }
  177.  
  178. shadow_empty_mems(mem)
  179. int mem ;
  180. {
  181.    if (mem == nil)   return;
  182.    shadow_empty_mems(BROTHER(mem));
  183.    if (no_derived_afx(AFFIXTREE(mem))) return;
  184.    if (DEF(mem) > BROTHER(init_one_star))
  185.      newnode (NODENAME(mem),brother,SON(mem),new_repr(REPR(mem)));
  186.    else
  187.      newdefnode (NODENAME(mem),brother,SON(mem),DEF(mem),REPR(mem));
  188. }
  189.  
  190. no_derived_afx(afx) 
  191. int afx;
  192. {
  193.    for (; afx != nil; afx = BROTHER(afx))
  194.      if (DERIVED(afx))
  195.        return false;
  196.    return true;
  197. }
  198.  
  199. char *new_repr(head)
  200. char *head;
  201. {
  202.    int             curchar;
  203.    hashindex = 0;
  204.    curchar = 0;
  205.    do {
  206.       chartable[charindex++] = *head;
  207.       hashindex += *head++ << (++curchar & 7);
  208.    } while (*head != '\0');
  209.    chartable[charindex++] = '_';
  210.    hashindex += '_' << (++curchar & 7);
  211.    
  212.    hashindex &= (maxnt - 1);
  213.    chartable[charindex++] = '\0';
  214.    addname();
  215.    return string;
  216. }
  217.  
  218. link_empty_rules()
  219. {
  220.    register int    rule,alt,mem,afx;
  221.    for (rule = first_empty_rule; rule != nil; rule = BROTHER(rule)) {
  222.       int alt = SON(rule);
  223.       for (; alt != nil; alt = BROTHER(alt)) 
  224.         link_empty_members(alt,rule);
  225.    }
  226. }
  227.  
  228. link_empty_members(alt,rule)
  229. int alt,rule;
  230. {
  231.    register int member,rrule;
  232.    for (member = SON(alt); member != nil; member = BROTHER(member)) {
  233.          if (DEF(member) != -1) continue;
  234.          rrule = first_empty_rule;
  235.          while (REPR(member) != REPR(rrule)) {
  236.             if (rrule == nil) {
  237.                fprintf(stderr," compiler error:line %d in %s: member `%s' is not defined\n",
  238.         LINE(alt), REPR(rule),REPR(member));
  239.                exit(10);
  240.             } else
  241.                rrule = BROTHER(rrule);
  242.          }
  243.          if (rrule == nil)
  244.             break;
  245.          DEF(member) = rrule;
  246.    }
  247. }
  248.  
  249. char *short_repr(count)
  250. int count;
  251. {
  252.    int             curchar;
  253.    char c1 = 'A'+ count%26;
  254.    hashindex = 0;
  255.    curchar = 0;
  256.    chartable[charindex++] = c1;
  257.    hashindex += c1 << (++curchar & 7);
  258.    chartable[charindex++] = '_';
  259.    hashindex += '_' << (++curchar & 7);
  260.    
  261.    hashindex &= (maxnt - 1);
  262.    chartable[charindex++] = '\0';
  263.    addname();
  264.    return string;
  265. }
  266.